from typing import List


class Solution:
    def respace(self, dictionary: List[str], sentence: str) -> int:
        ls = len(sentence)
        ld = len(dictionary)
        ans = 0
        dp = [-1 for i in range(ls+1)]
        dp[0] = 0

        for i in range(ls+1):
            for j in range(0, i):
                if dp[i] == -1 or dp[j] + i-j < dp[i]:
                    dp[i] = dp[j] + i-j
            for j in range(ld):
                lw = len(dictionary[j])
                # if i+lw < ls and sentence[i:i+lw] == dictionary[j]:
                if sentence[i:i + lw] == dictionary[j]:
                    # if dp[i+lw] == -1 or dp[i+lw] > dp[i]:
                    if dp[i+lw] == -1 or dp[i+lw] > dp[i]:
                        dp[i+lw] = dp[i]
        ans = dp[ls]

        return ans


solve = Solution()

questions = [
    (["looked", "just", "like", "her", "brother"], 'jesslookedjustliketimherbrother', ),
    (["potimzz"], "potimzzpotimzz"),
    (["abc"], "abcabc"),

]

for qi, q in enumerate(questions, 1):
    print(f'#{qi}:', q)
    print(solve.respace(q[0], q[1]))
